|
In mathematics and computer algebra, factorization of polynomials or polynomial factorization is the process of expressing a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in same domain. Polynomial factorization is one of the fundamental tools of the computer algebra systems. The history of polynomial factorization starts with Hermann Schubert who in 1793 described the first polynomial factorization algorithm, and Leopold Kronecker, who rediscovered Schubert's algorithm in 1882 and extended it to multivariate polynomials and coefficients in an algebraic extension. But most of the knowledge on this topic is not older than circa 1965 and the first computer algebra systems. In a survey of the subject, Erich Kaltofen wrote in 1982 (see the bibliography, below):
Nowadays〔An example of degree 2401, taking 7.35 seconds, is found in Section 4 in: Hart, van Hoeij, Novocin: ''Practical Polynomial Factoring in Polynomial Time'' ISSAC'2011 Proceedings, p. 163-170 (2011).〕 one can quickly factor any univariate polynomial of degree 1000, and coefficients with thousands of digits. ==Formulation of the question== Polynomial rings over the integers or over a field are unique factorization domains. This means that every element of these rings is a product of a constant and a product of irreducible polynomials (those that are not the product of two non-constant polynomials). Moreover, this decomposition is unique up to multiplication of the factors by invertible constants. Factorization depends on the base field. For example, the fundamental theorem of algebra, which states that every polynomial with complex coefficients has complex roots, implies that a polynomial with integer coefficients can be factored (with root-finding algorithms) into linear factors over the complex field C. Similarly, over the field of reals, the irreducible factors have degree at most two, while there are polynomials of any degree that are irreducible over the field of rationals Q. The question of polynomial factorization makes sense only for coefficients in a ''computable field'' whose every element may be represented in a computer and for which there are algorithms for the arithmetic operations. Fröhlich and Shepherson have provided examples of such fields for which no factorization algorithm can exist. The fields of coefficients for which factorization algorithms are known include prime fields (i.e. the field of rationals and prime modular arithmetic) and their finitely generated field extensions. Integer coefficients are also tractable. Kronecker's classical method is interesting only from a historical point of view; modern algorithms proceed by a succession of: * Square-free factorization * Factorization over finite fields and reductions: * From the multivariate case to the univariate case. * From coefficients in a purely transcendental extension to the multivariate case over the ground field (see below). * From coefficients in an algebraic extension to coefficients in the ground field (see below). * From rational coefficients to integer coefficients (see below). * From integer coefficients to coefficients in a prime field with ''p'' elements, for a well chosen ''p'' (see below). ==Primitive part–content factorization== In this section, we show that factoring over Q (the rational numbers) and over Z (the integers) is essentially the same problem. The ''content'' of a polynomial ''p'' ∈ Z(), denoted "cont(''p'')", is, up to its sign, the greatest common divisor of its coefficients. The ''primitive part'' of ''p'' is primpart(''p'')=''p''/cont(''p''), which is a primitive polynomial with integer coefficients. This defines a factorization of ''p'' into the product of an integer and a primitive polynomial. This factorization is unique up to the sign of the content. It is a usual convention to choose the sign of the content such that the leading coefficient of the primitive part is positive. For example, : is a factorization into content and primitive part. Every polynomial ''q'' with rational coefficients may be written : where ''p'' ∈ Z() and ''c'' ∈ Z: it suffices to take for ''c'' a multiple of all denominators of the coefficients of ''q'' (for example their product) and ''p'' = ''cq''. The ''content'' of ''q'' is defined as: : and the ''primitive part'' of ''q'' is that of ''p''. As for the polynomials with integer coefficients, this defines a factorization into a rational number and a primitive polynomial with integer coefficients. This factorization is also unique up to the choice of a sign. For example, : is a factorization into content and primitive part. Gauss proved that the product of two primitive polynomials is also primitive (Gauss's lemma). This implies that a primitive polynomial is irreducible over the rationals if and only if it is irreducible over the integers. This implies also that the factorization over the rationals of a polynomial with rational coefficients is the same as the factorization over the integers of its primitive part. On the other hand, the factorization over the integers of a polynomial with integer coefficients is the product of the factorization of its primitive part by the factorization of its content. In other words, integer GCD computation allows to reduce the factorization of a polynomial over the rationals to the factorization of a primitive polynomial with integer coefficients, and to reduce the factorization over the integers to the factorization of an integer and a primitive polynomial. Everything that precedes remains true if Z is replaced by a polynomial ring over a field ''F'' and Q is replaced by a field of rational functions over ''F'' in the same variables, with the only difference that "up to a sign" must be replaced by "up to the multiplication by an invertible constant in ''F''". This allows to reduce the factorization over a purely transcendental field extension of ''F'' to the factorization of multivariate polynomials over ''F''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「factorization of polynomials」の詳細全文を読む スポンサード リンク
|